Queue Using Linked List Algorithm
The Queue Using Linked List Algorithm is a data structure that implements the queue abstract data type using a doubly linked list as its underlying structure. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where the first element added to the queue is the first one to be removed. This algorithm provides efficient operations for enqueueing (adding an element to the rear of the queue) and dequeueing (removing the element from the front of the queue) elements, as well as peeking (retrieving the value of the front element without removing it) and checking if the queue is empty.
In the Queue Using Linked List Algorithm, the doubly linked list consists of nodes, where each node contains a data value and two pointers: one pointing to the previous node and one pointing to the next node in the queue. The queue maintains a reference to the front and rear nodes to enable quick access and manipulation of elements. To enqueue an element, a new node is created, and its pointers are updated to link it to the rear node of the queue. The rear pointer is then updated to point to the newly added node. To dequeue an element, the front node is removed, and the front pointer is updated to point to the next node in the queue. The time complexity of enqueue and dequeue operations in this algorithm is O(1) as they involve only constant-time pointer updates.
#include <iostream>
using namespace std;
struct node
{
int val;
node *next;
};
node *front, *rear;
void Enque(int x)
{
if (rear == NULL)
{
node *n = new node;
n->val = x;
n->next = NULL;
rear = n;
front = n;
}
else
{
node *n = new node;
n->val = x;
n->next = NULL;
rear->next = n;
rear = n;
}
}
void Deque()
{
if (rear == NULL && front == NULL)
{
cout << "\nUnderflow";
}
else
{
node *t = front;
cout << "\n"
<< t->val << " deleted";
front = front->next;
delete t;
if (front == NULL)
rear = NULL;
}
}
void show()
{
node *t = front;
while (t != NULL)
{
cout << t->val << "\t";
t = t->next;
}
}
int main()
{
int ch, x;
do
{
cout << "\n1. Enque";
cout << "\n2. Deque";
cout << "\n3. Print";
cout << "\nEnter Your Choice : ";
cin >> ch;
if (ch == 1)
{
cout << "\nInsert : ";
cin >> x;
Enque(x);
}
else if (ch == 2)
{
Deque();
}
else if (ch == 3)
{
show();
}
} while (ch != 0);
return 0;
}
